package com.liang.leetcode.binarytree.exercise;

import com.liang.leetcode.binarytree.entity.TreeNode;
import com.liang.leetcode.binarytree.util.BiTreeUtil;

import java.util.*;

/**
 * 404.左叶子之和
 */
public class BiTree13_SumOfLeftLeaves {
    public static void main(String[] args) {
        // 创建一棵二叉树
        List<Integer> nodeList = Arrays.asList(3, 9, 20, null, null, 15, 7);
        TreeNode root = BiTreeUtil.createBiTreeByRecursion(nodeList);
        System.out.println("先序遍历：" + BiTreeUtil.preorderTraversal(root));
        // 二叉树的左叶子之和
        System.out.println(sumOfLeftLeaves2(root));
    }

    /**
     * 递归：用前序遍历，求树上所有左叶子节点的和
     * 通过节点的父节点来判断其左孩子是不是左叶子
     */
    private static int sumOfLeftLeaves(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 初始化当前节点的左叶子节点值为0
        int leftValue = 0;
        // 如果当前节点的左子节点存在且为叶子节点，则累加其值
        if (root.left != null && root.left.left == null && root.left.right == null) {
            leftValue += root.left.val;
        }
        // 递归计算左子树和右子树的左叶子节点之和，并与当前节点的左叶子节点值相加
        return leftValue + sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
    }

    /**
     * 迭代：栈 / 队列
     */
    private static int sumOfLeftLeaves2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftValue = 0;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            // 判断左节点是否为左叶子节点
            if (node.left != null && node.left.left == null && node.left.right == null) {
                leftValue += node.left.val;
            }
            // 左右节点入栈
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        return leftValue;
    }

    public static int sumOfLeftLeaves3(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftValue = 0;
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            // 判断左节点是否为左叶子节点
            if (node.left != null && node.left.left == null && node.left.right == null) {
                leftValue += node.left.val;
            }
            // 左右节点入队
            if (node.right != null) {
                queue.offer(node.right);
            }
            if (node.left != null) {
                queue.offer(node.left);
            }
        }
        return leftValue;
    }

}
